The popularity of distributed databases or ledgers, such as blockchain and its derivatives, to provide decentralized secure records that are based on cryptographic proofs instead of trust has been steadily increasing in recent years. In such environments, individuals can typically enter directly into transactions with each other without the need for a trusted third party to serve as an intermediary for verifying the authenticity of the transaction.
A blockchain is a data structure composed of a chronological chain of blocks. Each block added to the chain typically contains a timestamp, a nonce, a hash of the immediately previous/last block added to the chain, and application-specific data, such as cryptocurrency transactions. Once a block is added to the chain, the block typically cannot be retroactively altered. As each block includes a hash of the immediately prior block in the chain, the hash of any given block in the chain depends on the entire prior history of the chain, forming a tamper-evident log.
As the number of transactions recorded in a blockchain increase over time, the size of the blockchain and the computing resources including memory and processor resources required to monitor and verify transactions on the blockchain also increase. For example, to verify the authenticity of a transaction between two parties on a blockchain it can be necessary that the device verifying the transaction download each block in the blockchain and verify the chain block-by-block. As a result, it can be difficult for resource constrained devices to efficiently and effectively interact with a blockchain over time. Alternatively, such resource constrained devices can cede or defer trust to a full-node. However, deferring trust to a full node to perform the verification results in a loss of the benefit of decentralized security.
In an attempt to reduce the burden of computing resources to monitor and/or verify transactions in convention blockchain-based systems, conventional blockchain-based system can employ Simplified Payment Verification (SPV), in which a verifying device downloads only the block headers (not full blocks) and a Merkle proof that a transaction of interest was included in a particular block of interest. However, the utilization of SPV can still impose a substantial bandwidth/power cost (particularly to light/thin client applications). For example, the verifying device may still have to download a new block header periodically (e.g., every ten minutes or so) for as long as the verifying device is following or monitoring the blockchain. The problem can be compounded in the event that the verifying device has not periodically downloaded new blocks as they are added to the blockchain, but wishes or needs to become current or “catch-up” by downloading and verifying the blocks added to the blockchain since the verifying device last downloaded a block. The computing resources required to catch-up can increase linearly over time without bound. For example, if the verifying device or a blockchain-following application needs to catch up with the blockchain after a long period (e.g., if it's been a month or a year since the user last ran the blockchain-following application), the quantity of new blocks added to the blockchain can increase in proportion to the period over which the new blocks were not downloaded.
Additionally, there are security weaknesses with SPV, because the SPV client is only verifying that it is seeing “a blockchain” representing a certain amount of Proof-of-Work. The SPV client does not have a way to verify that it is actually seeing the same proof-of-work blockchain that the rest of the world is seeing. As a result, a sufficiently well-motivated attacker could invest the time required to create an alternate history with the amount of work needed to trick an SPV client.